package com.tgy.algorithm.base._排序;

import java.util.Arrays;

public class _插入排序 {

    public static void insertSort(int[] nums) {

        if (nums == null || nums.length == 0 || nums.length == 1) {
            return;
        }

        int len = nums.length;

        for (int i = 1; i < len; i++) {

            int index = findGT(nums,i);
            if (index != -1) {
                int value = nums[i];
                int idx = i;
                while (idx > index) {
                    nums[idx] = nums[idx - 1];
                    idx--;
                }
                nums[index] = value;
            }
        }
    }

    public static int findGT(int[] nums,int index) {

        int retIndex = -1;
        int value = nums[index];
        int leftIndex = 0;
        int rightIndex = index - 1;

        while (leftIndex <= rightIndex) {
            int mid = leftIndex + ((rightIndex  - leftIndex) >> 1);
            if (nums[mid] > value) {
                retIndex = mid;
                rightIndex = mid - 1;
            }else {
                leftIndex = mid + 1;
            }
        }

        return retIndex;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{2,3,1,4,8,5,3};
        insertSort(nums);
        System.out.println(Arrays.toString(nums));
    }
}
